505. The Maze II
Medium

There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the m x n maze, the ball's start position and the destination, where start = [startrow, startcol] and destination = [destinationrow, destinationcol], return the shortest distance for the ball to stop at the destination. If the ball cannot stop at destination, return -1.

The distance is the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included).

You may assume that the borders of the maze are all walls (see examples).

 

Example 1:

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: 12
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
The length of the path is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.

Example 2:

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
Output: -1
Explanation: There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.

Example 3:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1]
Output: -1

 

Constraints:

  • m == maze.length
  • n == maze[i].length
  • 1 <= m, n <= 100
  • maze[i][j] is 0 or 1.
  • start.length == 2
  • destination.length == 2
  • 0 <= startrow, destinationrow <= m
  • 0 <= startcol, destinationcol <= n
  • Both the ball and the destination exist in an empty space, and they will not be in the same position initially.
  • The maze contains at least 2 empty spaces.
Accepted
62,961
Submissions
127,878
Seen this question in a real interview before?
Companies
Similar Questions

Average Rating: 4.74 (61 votes)

Solution


Approach #1 Depth First Search [Accepted]

We can view the given search space in the form of a tree. The root node of the tree represents the starting position. Four different routes are possible from each position i.e. left, right, up or down. These four options can be represented by 4 branches of each node in the given tree. Thus, the new node reached from the root traversing over the branch represents the new position occupied by the ball after choosing the corresponding direction of travel.

Maze_Tree

In order to do this traversal, one of the simplest schemes is to undergo depth first search. We make use of a recursive function dfs for this. From every current position, we try to go as deep as possible into the levels of a tree taking a particular branch traversal direction as possible. When one of the deepest levels is exhausted, we continue the process by reaching the next deepest levels of the tree. In order to travel in the various directions from the current position, we make use of a dirsdirs array. dirsdirs is an array with 4 elements, where each of the elements represents a single step of a one-dimensional movement. For travelling in a particular direction, we keep on adding the appropriate dirsdirs element in the current position till the ball hits a boundary or a wall.

We start with the given startstart position, and try to explore these directions represented by the dirsdirs array one by one. For every element dirdir of the dirsdirs chosen for the current travelling direction, we determine how far can the ball travel in this direction prior to hitting a wall or a boundary. We keep a track of the number of steps using countcount variable.

Apart from this, we also make use of a 2-D distancedistance array. distance[i][j]distance[i][j] represents the minimum number of steps required to reach the positon (i,j)(i, j) starting from the startstart position. This array is initialized with largest integer values in the beginning.

When we reach any position next to a boundary or a wall during the traversal in a particular direction, as discussed earlier, we keep a track of the number of steps taken in the last direction in countcount variable. Suppose, we reach the position (i,j)(i,j) starting from the last position (k,l)(k,l). Now, for this position, we need to determine the minimum number of steps taken to reach this position starting from the startstart position. For this, we check if the current path takes lesser steps to reach (i,j)(i,j) than any other previous path taken to reach the same position i.e. we check if distance[k][l]+countdistance[k][l] + count is lesser than distance[i][j]distance[i][j]. If not, we continue the process of traversal from the position (k,l)(k,l) in the next direction.

If distance[k][l]+countdistance[k][l] + count is lesser than distance[i][j]distance[i][j], we can reach the position (i,j)(i,j) from the current route in lesser number of steps. Thus, we need to update the value of distance[i][j]distance[i][j] as distance[k][l]+countdistance[k][l] + count. Further, now we need to try to reach the destination, destdest, from the end position (i,j)(i,j), since this could lead to a shorter path to destdest. Thus, we again call the same function dfs but with the position (i,j)(i,j) acting as the current position.

After this, we try to explore the routes possible by choosing all the other directions of travel from the current position (k,l)(k,l) as well.

At the end, the entry in distance array corresponding to the destination, destdest's coordinates gives the required minimum distance to reach the destination. If the destination can't be reached, the corresponding entry will contain \text{Integer.MAX_VALUE}.

The following animation depicts the process.

Current
1 / 31

Complexity Analysis

  • Time complexity : O(mnmax(m,n))O(m*n*\text{max}(m,n)). Complete traversal of maze will be done in the worst case. Here, mm and nn refers to the number of rows and columns of the maze. Further, for every current node chosen, we can travel upto a maximum depth of max(m,n)\text{max}(m,n) in any direction.

  • Space complexity : O(mn)O(mn). distancedistance array of size mnm*n is used.


Approach #2 Using Breadth First Search [Accepted]

Algorithm

Instead of making use of Depth First Search for exploring the search space, we can make use of Breadth First Search as well. In this, instead of exploring the search space on a depth basis, we traverse the search space(tree) on a level by level basis i.e. we explore all the new positions that can be reached starting from the current position first, before moving onto the next positions that can be reached from these new positions.

In order to make a traversal in any direction, we again make use of dirsdirs array as in the DFS approach. Again, whenever we make a traversal in any direction, we keep a track of the number of steps taken while moving in this direction in countcount variable as done in the last approach. We also make use of distancedistance array initialized with very large values in the beginning. distance[i][j]distance[i][j] again represents the minimum number of steps required to reach the position (i,j)(i,j) from the startstart position.

This approach differs from the last approach only in the way the search space is explored. In order to reach the new positions in a Breadth First Search order, we make use of a queuequeue, which contains the new positions to be explored in the future. We start from the current position (k,l)(k,l), try to traverse in a particular direction, obtain the corresponding countcount for that direction, reaching an end position of (i,j)(i,j) just near the boundary or a wall. If the position (i,j)(i,j) can be reached in a lesser number of steps from the current route than any other previous route checked, indicated by distance[k][l]+count<distance[i][j]distance[k][l] + count < distance[i][j], we need to update distance[i][j]distance[i][j] as distance[k][l]+countdistance[k][l] + count.

After this, we add the new position obtained, (i,j)(i,j) to the back of a queuequeue, so that the various paths possible from this new position will be explored later on when all the directions possible from the current position (k,l)(k,l) have been explored. After exploring all the directions from the current position, we remove an element from the front of the queuequeue and continue checking the routes possible through all the directions now taking the new position(obtained from the queuequeue) as the current position.

Again, the entry in distance array corresponding to the destination, destdest's coordinates gives the required minimum distance to reach the destination. If the destination can't be reached, the corresponding entry will contain \text{Integer.MAX_VALUE}.

Complexity Analysis

  • Time complexity : O(mnmax(m,n))O(m*n*max(m,n)). Time complexity : O(mnmax(m,n))O(m*n*\text{max}(m,n)). Complete traversal of maze will be done in the worst case. Here, mm and nn refers to the number of rows and columns of the maze. Further, for every current node chosen, we can travel upto a maximum depth of max(m,n)\text{max}(m,n) in any direction.

  • Space complexity : O(mn)O(mn). queuequeue size can grow upto mnm*n in the worst case.


Approach #3 Using Dijkstra Algorithm [Accepted]

Algorithm

Before we look into this approach, we take a quick overview of Dijkstra's Algorithm.

Dijkstra's Algorithm is a very famous graph algorithm, which is used to find the shortest path from any startstart node to any destinationdestination node in the given weighted graph(the edges of the graph represent the distance between the nodes).

The algorithm consists of the following steps:

  1. Assign a tentative distance value to every node: set it to zero for our startstart node and to infinity for all other nodes.

  2. Set the startstart node as currentcurrent node. Mark it as visited.

  3. For the currentcurrent node, consider all of its neighbors and calculate their tentative distances. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one to all the neighbors. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value.

  4. When we are done considering all of the neighbors of the current node, mark the currentcurrent node as visited. A visited node will never be checked again.

  5. If the destinationdestination node has been marked visited or if the smallest tentative distance among all the nodes left is infinity(indicating that the destinationdestination can't be reached), then stop. The algorithm has finished.

  6. Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new currentcurrent node, and go back to step 3.

The working of this algorithm can be understood by taking two simple examples. Consider the first set of nodes as shown below.

Dijkstra_Graph

Suppose that the node bb is at a shorter distance from the startstart node aa as compared to cc, but the distance from aa to the destinationdestination node, ee, is shorter through the node cc itself. In this case, we need to check if the Dijkstra's algorithm works correctly, since the node bb is considered first while selecting the nodes being at a shorter distance from aa. Let's look into this.

  1. Firstly, we choose aa as the startstart node, mark it as visited and update the distancebdistance_b and distancecdistance_c values. Here, distanceidistance_i represents the distance of node ii from the startstart node.

  2. Since distanceb<distancecdistance_b < distance_c, bb is chosen as the next node for calculating the distances. We mark bb as visited. Now, we update the distanceedistance_e value as distanceb+weightbedistance_b + weight_{be}.

  3. Now, cc is obviously the next node to be chosen as per the conditions of the assumptions taken above. (For path to ee through cc to be shorter than path to ee through cc, distancec<distanceb+weightbedistance_c < distance_b + weight_{be}. From cc, we determine the distance to node ee. Since distancec+weightcedistance_c + weight_{ce} is shorter than the previous value of distanceedistance_e, we update distanceedistance_e with the correct shorter value.

  4. We choose ee as the current node. No other distances need to be updated. Thus, we mark ee as visited. distanceedistance_e now gives the required shortest distance.

The above example proves that even if a locally closer node is chosen as the current node first, the ultimate shortest distance to any node is calculated correctly.

Let's take another example to demonstrate that the visited node needs not be chosen again as the current node.

Dijkstra_Graph

Suppose aa is the startstart node and ee is the destinationdestination node. Now, suppose we visit bb first and mark it as visited, but later on we find that another path exists through cc to bb, which makes the distancebdistance_b shorter than the previous value. But, because of this, we need to consider bb as the current node again, since it would affect the value of distanceedistance_e. But, if we observe closely, such a situation would never occur, because for weightac+weightcbweight_{ac} + weight_{cb} to be lesser than weightabweight_{ab}, weightac<weightabweight_{ac} < weight_{ab} in the first place. Thus, bb would never be marked visitedvisited before cc, which contradicts the first assumption. This proves that the visitedvisited node needs not be chosen as the current node again.

The given problem is also a shortest distance finding problem with a slightly different set of rules. Thus, we can make use of Dijkstra's Algorithm to determine the minimum number of steps to reach the destination.

The methodology remains the same as the DFS or BFS Approach discussed above, except the order in which the current positions are chosen. We again make use of a distancedistance array to keep a track of the minimum number of steps needed to reach every position from the startstart position. At every step, we choose a position which hasn't been marked as visited and which is at the shortest distance from the startstart position to be the current position. We mark this position as visited so that we don't consider this position as the current position again.

From the current position, we determine the number of steps required to reach all the positions possible travelling from the current position(in all the four directions possible till hitting a wall/boundary). If it is possible to reach any position through the current route with a lesser number of steps than the earlier routes considered, we update the corresponding distancedistance entry. We continue the same process for the other directions as well for the current position.

In order to determine the current node, we make use of minDistance function, in which we traverse over the whole distancedistance array and find out an unvisited node at the shortest distance from the startstart node.

At the end, the entry in distancedistance array corresponding to the destinationdestination position gives the required minimum number of steps. If the destination can't be reached, the corresponding entry will contain \text{Integer.MAX_VALUE}.

**Complexity Analysis**
  • Time complexity : O((mn)2)O((mn)^2). Complete traversal of maze will be done in the worst case and function minDistance takes O(mn)O(mn) time.

  • Space complexity : O(mn)O(mn). distancedistance array of size mnm*n is used.


Approach #4 Using Dijkstra Algorithm and Priority Queue[Accepted]

Algorithm

In the last approach, in order to choose the current node, we traversed over the whole distancedistance array and found out an unvisited node at the shortest distance from the startstart node. Rather than doing this, we can do the same task much efficiently by making use of a Priority Queue, queuequeue. This priority queue is implemented internally in the form of a heap. The criteria used for heapifying is that the node which is unvisited and at the smallest distance from the startstart node, is always present on the top of the heap. Thus, the node to be chosen as the current node, is always present at the front of the queuequeue.

For every current node, we again try to traverse in all the possible directions. We determine the minimum number of steps(till now) required to reach all the end points possible from the current node. If any such end point can be reached in a lesser number of steps through the current path than the paths previously considered, we need to update its distancedistance entry.

Further, we add an entry corresponding to this node in the queuequeue, since its distancedistance entry has been updated and we need to consider this node as the competitors for the next current node choice. Thus, the process remains the same as the last approach, except the way in which the pick out the current node(which is the unvisited node at the shortest distance from the startstart node).

**Complexity Analysis**
  • Time complexity : O(mnlog(mn))O\big(mn*log(mn)\big). Complete traversal of maze will be done in the worst case giving a factor of mnmn. Further, poll method is a combination of heapifying(O(log(n))O\big(log(n)\big)) and removing the top element(O(1)O(1)) from the priority queue, and it takes O(n)O(n) time for nn elements. In the current case, poll introduces a factor of log(mn)log(mn).

  • Space complexity : O(mn)O(mn). distancedistance array of size mnm*n is used and queuequeue size can grow upto mnm*n in worst case.

Report Article Issue

Comments: 47
ColinBin's avatar
Read More

I'm not sure if the time complexity for Approach #1 is correct. Consider we go from s to t, at first we choose s's neighbor a as the next start point, and we went all the way down to t (s-a-n-t), and we call this path p. When we trace back to s, we then choose s's neighbor b as the next start point, and we may find out that after we go a few steps, we find we reach a node n on path p and the distance we have gone so far is smaller, so we have to update the rest of p util we finally update t (b-n-t). Revisiting could happen O(m * n) times, and the path could be of length O(m * n), should the time complexity be O(mnm*n)?

15
Show 3 replies
Reply
Share
Report
quan321's avatar
Read More

Hey vinod! Why the BFS solution does not check the position already visited? Is that because the distance needs to be updated? @vinod23

18
Show 7 replies
Reply
Share
Report
dr_pro's avatar
Read More

Please discard the last reply (leetcode doesn't allow edit comment : (. Shouldn't you consider the time wasted on visiting the same node multiple times in Approach 2? Also, I think your time complexity for approach 4 is wrong, you still have to find neighbors so the max(m, n) should appear as well, right?

8
Reply
Share
Report
stevenzhang0's avatar
Read More

What's the point of using dijkstra for this problem if the edges aren't weighted? Won't that just give us the same result, time complexity, space complexity, as BFS, just with worse code readability?

9
Show 3 replies
Reply
Share
Report
haoyangfan's avatar
Read More

My simplified version of Dijkstra Algorithm, where I replace the use of dist int array with a boolean array visited which simply keep track of nodes we've visited, which mean that we've already found the shortest path to it

class Solution {
    private int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int rows = maze.length, cols = maze[0].length;
        int s = start[0] * cols + start[1];
        int target = destination[0] * cols + destination[1];
        Queue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        boolean[] visited = new boolean[rows * cols];
        // length 2 array: first element -> index (1D), 2nd element -> path cost 
        pq.offer(new int[]{s, 0});
        // visited[s] = true;
        while (!pq.isEmpty()) {
            
            // Dijkstra algorithm: the time we pop some element from the priroty queue 
            // we are guaranteed to find the minimum path cost to it 
            int[] curr = pq.poll();
            visited[curr[0]] = true;
            if (curr[0] == target) return curr[1];
            
            int currIdx = curr[0], currCost = curr[1];
            int r = currIdx / cols, c =  currIdx % cols;
            for (int[] direction : directions) {
                int rr = r, cc = c, num = 0;
                while (isValid(rr + direction[0], cc + direction[1], rows, cols, maze)) {
                    rr += direction[0];
                    cc += direction[1];
                    num += 1;
                }
                if (num == 0) continue;
                int next = rr * cols + cc;
                if (visited[next]) continue;
                pq.offer(new int[]{next, currCost + num});
            }
        }
        return -1;
    }
    
    private boolean isValid(int r, int c, int rows, int cols, int[][] maze) {
        return r >= 0 && r < rows && c >= 0 && c < cols && maze[r][c] == 0;
    }
}

5
Show 1 reply
Reply
Share
Report
bearicc's avatar
Read More

In the second BFS solution, it is possible to visit the same node multiple times.

5
Reply
Share
Report
dr_pro's avatar
Read More

Shouldn't you consider the time wasted on visiting the same node multiple times in Approach 2? Also, I think your time complexity for approach is wrong, you still have to find neighbors so the max(m, n)/(m + n) should appear as well, right?

4
Reply
Share
Report
sona123's avatar
Read More

For the BFS approach, why is the time complexity of Maze 1 O(mn) and for Maze 2 its O(mn*max(m, n)).
Can someone please clarify?

3
Show 1 reply
Reply
Share
Report
GraceMeng's avatar
Read More

My implementation of Dijkstra + PriorityQueue is as below, and I think it more understandable :

    private final static int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int[][] minDist = new int[maze.length][maze[0].length];
        for (int[] row : minDist) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        minDist[start[0]][start[1]] = 0;
        dijkstra(minDist, start, maze);
        return minDist[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 : minDist[destination[0]][destination[1]];
    }

    private static void dijkstra(int[][] minDist, int[] start, int[][] maze) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        pq.offer(new int[]{start[0], start[1], 0});
        while (!pq.isEmpty()) {
            int[] minVer = pq.poll();
//            if (minDist[minVer[0]][minVer[1]] < minVer[2]) {
//                continue;
//            }

            for (int[] dir : directions) {
                int nx = minVer[0];
                int ny = minVer[1];
                int curDist = 0;
                while (nx + dir[0] >= 0 && ny + dir[1] >= 0 && nx + dir[0] < minDist.length && ny + dir[1] < minDist[0].length && maze[nx + dir[0]][ny + dir[1]] == 0) {
                    nx += dir[0];
                    ny += dir[1];
                    curDist++;
                }
                if (minDist[minVer[0]][minVer[1]] != Integer.MAX_VALUE && minDist[nx][ny] > minDist[minVer[0]][minVer[1]] + curDist) {
                    minDist[nx][ny] = minDist[minVer[0]][minVer[1]] + curDist;
                    pq.offer(new int[]{nx, ny, minDist[nx][ny]});
                }
            }
        }
    }

3
Show 1 reply
Reply
Share
Report
atifnawab's avatar
Read More

i'm not able to understand how they are computing the distance, can anybody help me with that ?

1
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
06/09/2021 08:55Accepted92 ms23.7 MBcpp
06/09/2021 08:55Accepted96 ms23.7 MBcpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.